package dp;

import org.junit.Test;

import java.util.Arrays;

// 题目链接: https://mp.weixin.qq.com/s/NZPaFsFrTybO3K3s7p7EVg
// 题目描述: 圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。
public class CircleBackToOrigin {

    @Test
    public void test() {
        System.out.println(backToOrigin(10, 2));
    }

    // dp[m][p] = dp[m-1][|p-1|] + dp[m-1][|p+1|]
    public int backToOrigin(int points, int steps) {
        int[][] dp = new int[steps+1][points];
        for (int[] a: dp) {
            Arrays.fill(a, 0);
        }
        dp[0][0] = 1;
        for (int m = 1; m <= steps; m++) {
            for (int p = 0; p < points; p++) {
                dp[m][p] = dp[m-1][(points+p-1) % points] + dp[m-1][(p+1) % points];
                System.out.format("dp[%d][%d]=%d\n", m, p, dp[m][p]);
            }
        }
        return dp[steps][0];
    }
}
